package 力扣._6953_判断能否拆分数组;

import java.util.ArrayList;
import java.util.List;

public class Solution3 {
    //思路错了，存在只有从非最小值划分才可以的情况，不会
    //暴力写个试试
    int sum(List<Integer> nums, int l, int r) {
        int sum = 0;
        for (int i = l; i <= r; i++) {
            sum += nums.get(i);
        }
        return sum;
    }

    //从最小值处向两侧拆
    boolean split(List<Integer> nums, int l, int r, int m) {
        //对上次划分结果进行判断：失败情况，长度大于1，且和小于m，成功情况：长度==1
        if (l == r)
            return true;
        else if (r - l > 0 && sum(nums, l, r) < m)
            return false;

        boolean isture = false;
        for (int i = l; i <= r; i++) {
            //每个都划分试试
            if (i == l)
                isture = isture || split(nums, l + 1, r, m);
            else if (i == r)
                isture = isture || split(nums, l, r - 1, m);
            else {
                //向左侧
                isture = isture || (split(nums, l, i, m) && split(nums, i + 1, r, m));
                //向右侧
                isture = isture || (split(nums, l, i - 1, m) && split(nums, i, r, m));
            }
        }
        return isture;
    }

    public boolean canSplitArray(List<Integer> nums, int m) {
        return split(nums, 0, nums.size() - 1, m);
    }

    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>();
        nums.add(3);
        nums.add(3);
        nums.add(2);
        nums.add(1);
        nums.add(7);
        boolean b = new Solution3().canSplitArray(nums, 8);
        System.out.println(b);
    }
}
